Computer networks such as local-area networks (LANs) and larger wide-area networks (WANs) route data packets from one station to another often through intermediate nodes. Recently network switches making switching decisions based on multiple OSI Layers have become favored for connecting different stations on a LAN or different LANs on a corporate backbone network. These network switches have a higher throughput than earlier hubs or repeaters since multiple connections may be dynamically made and broken between different pairs of network nodes as needed, and they significantly reduce network congestion experienced in the shared media.
FIG. 1 is a diagram of a prior-art system that configures a network switch based on a search of a routing table using a microprocessor. Routing table 20 contains entries for different network addresses. These entries may be for lower-level media-access-controller (MAC) addresses on a LAN or higher-level Internet-Protocol (IP) addresses for a WAN. Each entry contains a MAC or IP address and a port number. Incoming packets to network switch 22 contain a destination address, such as a MAC and/or IP address. For some switches capable of performing multi-layered switching, the IP address may only be searched if the MAC address matches. The traditional routers are networked devices, and they only do IP-address searches. This destination address from the incoming packet is compared to the addresses in the entries in routing table 20 until a match is found. Then the port number for the matching entry is used to configure network switch 22, so that the data from the incoming port is forwarded to the output port identified by the port number from the matching entry in routing table 22.
Central processing unit (CPU) 10 monitors the input ports of network switch 22 for incoming packets. When an incoming packet is detected, CPU 10 reads the destination address of the new packet. Then CPU 10 executes a search routine to look for a matching entry in routing table 20. Once a matching entry is found, CPU 10 sends instructions to network switch 22 over bus 16 to establish a connection between the input port receiving the new input packet and the output port identified by the port number from the matching entry in routing table 20.
When CPU 10 is a general-purpose processor, CPU instructions are read from memory 12 over bus 16 before CPU 10 executes each instruction. The search routine is a series of such instructions contained in code block 18 in memory 12. For each entry in routing table 20, several instructions are fetched from code block 18, and the entry itself is read from routing table 20 in memory 12. Thus several accesses of memory 12 over bus 16 are required. Caching of instructions in CPU 10 can reduced traffic on bus 16, but usually caches are not large enough to contain routing table 20.
For each entry in routing table 20, the entry must be read from routine table 20 and compared to the destination address, which is stored in a register in CPU 10. Within CPU 10, arithmetic-logic-unit (ALU) 14 compares the destination address to the address in the entry read from routing table 20. This compare is repeated for each entry read from routing table 20 until a match is found.
Thus many accesses of memory 12 by CPU 10 are required to search routing table 20. Other incoming packets for other input ports may be detected before the search is complete. The search for these other incoming packets may need to be delayed until the first search is completed. Thus the delay or latency for these subsequent packets is increased. System throughput may be decreased, or a faster, more expensive CPU is needed to reduce delay and latency. However, the search must still be performed serially resulting in ports waiting in long queues while waiting for the CPU to finish the on-going search.
Some hardware-assisted search chips (integrated circuits) are being developed. For example, a dedicated search engine may be used rather than ALU 14 in CPU 10. This dedicated search engine can be directly coupled to the memory containing routing table 20. While this hardware improves the efficiency of the search engine compared to using the CPU, it does not solve the problem of serial search. Furthermore, the speed of the search is limited by the bandwidth (number of pins allocated to the table memory).
Embedded-DRAM Graphics Display Systems
The assignee has recognized the problem of bottlenecks to external dynamic-random-access memory (DRAM) in graphics display systems, and has pioneered embedded DRAM for graphics controllers. See for example: Puar et al., "Graphics Controller Integrated Circuit Without Memory Interface", U.S. Pat. Nos. 5,650,955 and 5,703,806. These embedded-DRAM graphics controllers have been used predominantly for portable PC's such as laptop and notebook PCs.
Although graphics controllers are in a different technical field hand network switches, the inventor has realized that such embedded DRAM technology could solve performance and cost problems for network switches. While many view embedded DRAM technology as useful only for portable systems, the inventor realizes that computer-network routers could benefit from the performance and cost improvement of embedded DRAM.
What is desired is a search engine for a network switch. It is desired to have a dedicated search engine search a network routing table for an entry with a matching MAC or IP address. It is further desired to use an embedded DRAM containing the routing table. It is desired to locate the search engine and the embedded DRAM on the same integrated circuit chip, allowing a very wide data path between the search engine and the routing table. It is further desired to increase the speed of the search engine by using an ultra-wide data path to the routing table. A parallel architecture for the search engine is also desired to allow searches for different input ports to occur at the same time, increasing throughput and decreasing latency. It is desired to provide a same low latency for all input ports even when other searches are in progress. A highly-parallel multiple-port search engine is desired.